The present invention relates generally to a graphics subsystem for a personal computer. More particularly, the present invention relates to a method and apparatus for manipulating the size of an image during three dimensional interpolated polygon rendering. Still more particularly, the present invention relates to a technique for dynamically switching mip-maps during polygon rendering based upon the depth parameter of each pixel to be drawn.
Before the availability of the personal computer (PC), computer graphics packages were expensive tools primarily reserved for industrial applications. Early microcomputers were only capable of rendering simple line drawings with a low screen resolution (256xc3x97256, for example). As microcomputers evolved, higher resolution color displays became available, and software applications routinely provided data output in a graphical manner. The graphics techniques used were unstructured, with objects defined in terms of absolute coordinates using straight lines. Subsequently, graphics xe2x80x9cprimitivesxe2x80x9d were used, enabling circles, ellipses, rectangles and polygons to be drawn with a single instruction. The use of primitives that can be rendered with a single instruction set of parameters has increased the speed at which the images can be rendered.
The availability of computer graphics has generated a demand for higher resolutions and three dimensional (3-D) rendering capabilities. Computer animation and games, in particular, have spawned a revolution in computer graphics capabilities. A 3-D image can be represented in a computer system as a collection of graphical objects, such as polygons, lines, and points. A set of vertex points defines a polygon. Associated with each point are certain pixel values, such as shading, texturing, color, and the like. Identification of other points within the polygon typically is done through the use of linear interpolation. Once interpolated, the polygon can be rendered on a computer monitor by successive scanning of orthogonal rows of the polygon.
Performing the linear interpolation calculations for each point (or pixel) of the polygon is very processor intensive. To minimize computations, polygon rendering typically is performed using a forward (or main) slope technique. Referring to the example of FIG. 6, a polygon 40 is divided into two adjacent triangles 47 and 49. The main slope technique requires the calculation of a main slope value (xcex94 main) which defines the slope of the side 45 that extends the entire vertical length of the triangle 40. Two opposite slopes are determined which represent the slopes of the other two sides 51, 53 of the triangle. A width slope value (xcex94 width) is calculated to define the incremental change in width for each successive orthogonal scan line (or row) of the polygon. An initial width value is provided for each triangle 47, 49 to represent the width of the first orthogonal scan for that triangle. Polygon 40 may also include depth values (or z values). An initial x and y value (x1, y1) defines the location of the initial vertex for the polygon, while the z value (z1) defines the depth. The z value is used to determine whether the image being rendered is in front of or behind other images, and thus determines whether the image will appear on the display, or whether it will be xe2x80x9chiddenxe2x80x9d behind another object. Other initial and slope values also may be generated to render the polygon, such as initial values for red, blue and green initial, and main and ortho slope values defining incremental variations in each color in both the x and y directions. Each of the triangles 47, 49 also has an associated count value to represent the number of scan lines required to render each triangle. In the preferred embodiment, the count value is determined by the y coordinate values of the vertex points. Thus, the upper count (COUNT 0) is found by subtracting y2 from y1. Similarly, the lower count value is determined by subtracting y3 from y2.
Each of the various initial and slope values typically are defined by a software graphics application driver, running on the host processor. Thus, the software driver, through the vehicle of the host processor, generates a xe2x80x9cdisplay listxe2x80x9d of parameters that are written to the graphics controller or processor. These parameters include, for example, the initial and slope values identified above. The graphics controller then uses the display list values in generating the graphics to be displayed.
In addition to the basic position and color parameters, graphics controllers are available which permit the texture of the polygon to be represented as part of the display. A texture may be defined as an image of a pattern generated by the software driver. Graphics controllers perform texture mapping by taking the pattern, which represents a flat image, and mapping the pattern in a curved or contoured manner. Thus, for example, the graphics application may require a particular pattern mapped to a teapot, or some other three dimensional object. In that case, the flat pattern image would be mapped to the teapot to represent the curved surface of the teapot, thus giving the illusion that the teapot is a three dimensional object.
When rendering in a three dimensional (3D) graphics application, such as a 3D animation application, a difficulty arises because the object moves. If the animation depicts relative movement of the object with respect to the viewer, (i.e. a person walking past a statue in a courtyard), then the distance between the object (the statue) and the viewer changes. To represent this change in distance, the object is rendered larger or smaller to reflect the viewer moving closer or further from it. To accomplish this type of rendering in 3D animation, different size versions of the object are generated, and a particular size version of the object is selected based upon the distance between the viewer and the object. The various size versions of the object are generated by the software driver by either compressing or expanding the image. Because resolution is lost when converting from a smaller to a larger image, the graphics application typically uses the largest possible image as the base image, so that smaller versions may be made by compressing the base image. Compression of the texture map is done through the use of filtering and averaging algorithms to compress the image. Thus, if the initial image was 512 bytes by 512 bytes (512xc3x97512), the map could be compressed to 256xc3x97256, 128xc3x97128, 64xc3x9764, or 32xc3x9732 or 16xc3x9716, for example, giving six different size images for the same object. Compression of each image is performed by taking a grouping of four pixels and averaging the pixel values to obtain a single pixel value. Each of the different size versions of the image are referred to as xe2x80x9cMip-maps.xe2x80x9d
In certain instances, several Mip-maps may be used to generate a polygon to provide a desired spatial relationship. Thus, for example, if the polygon being rendered is a brick wall that extends into the distance, it may be desirable to use different Mip-maps for different sections of the wall to make the bricks appear smaller for each section extending in the distance. Thus, initially, a first Mip-map of 256xc3x97256 may be used to render the first section of the wall. The section of the wall that is further away may then be rendered using a second Mip-map of 128xc3x97128. Proceeding further down the wall, it may be desirable to use a third Mip-map of 64xc3x9764. Thus, for objects that extend into the distance, it may be desirable to use different Mip-maps for patterns to add a sense of realism to the graphics display.
For most implementations of Mip-maps, the image is partitioned based upon the mip-maps and each mip-map partitions independently drawn. In addition, a separate set of interpolators and comparators are provided that track the location of the pixel being generated, and switch between Mip-maps based upon pixel location. The use of interpolators and comparators increases the number of gates required to implement the hardware and/or increases the number of clock cycles required to execute the software application. Thus, the interpolators required to switch between Mip-maps add to the overhead involved in generating the graphics display. It would be advantageous if mip-maps could be switched without the necessity of an inordinate number of additional gates.
In addition, it would be advantageous if the polygon could be rendered without breaking it into smaller polygons corresponding to the different Mip-maps. Partitioning the polygon into multiple sections and rendering these sections individually greatly increases the amount of time required to render the object. Instead, it would be advantageous if the object could be rendered with a single instruction by dynamically switching from one Mip-map to another without dissecting the object.
The present invention provides a system for dynamically switching Mip-maps for 3D polygon rendering without requiring the polygon to be dissected into Mip-map blocks. In accordance with the preferred embodiment, the present invention monitors the depth value (z) and selects the appropriate Mip-map based upon the measured depth value. Preferably, a graphics processor couples to the system bus for receiving a display list from the host processor providing parameters on the primitive to be drawn. Based upon the depth value (z) of the pixel to be rendered, the graphics processor dynamically selects a Mip-map to use in rendering the pixel, thus permitting multiple mip-maps to be used with single instruction rendering of the polygon.
The graphics processor preferably includes a register file for storing the display list parameters for a primitive, and a 3D engine which receives the display list parameters and generates values to enable rendering of the polygon. The 3D engine preferably includes an interpolation engine to generate x, y, z, r, g, b, u, and v values for each pixel from the initial and slope values provided in the display list. The z value is provided as an input to a Mip-map select logic, to select the Mip-map to be used to render that particular pixel. In the preferred embodiment, the Mip-map select logic includes a plurality of registers which are loaded with predetermined depth values. The depth registers define depth ranges for each of the Mip-maps. The z value for the pixel to be rendered is compared to the depth values in the depth registers in an associated comparator. A select logic selects the Mip-map based upon the results of the comparisons and provides a SHIFT output signal indicating the Mip-map selected, and the order of change from a base mip-map image.
In the preferred embodiment a texture engine receives the SHIFT signal and generates a texture map based upon the SHIFT value provided by the select logic. In addition to selecting the Mip-map, the SHIFT signal also is used to modify texture parameters to enable quick retrieval of the appropriate texture map for the selected mip map. The texture engine generates modified texture values uxe2x80x2 and vxe2x80x2, based upon the initial u and v values generated by the interpolation engines. The modified values uxe2x80x2, vxe2x80x2 values a number of bits defined by the contents of the SHIFT signal. The appropriate texture map is read from memory using the address of the base mip-map selected, and the modified texture parameters.
The present invention can be implemented either in hardware or in software. Thus, the graphics controller may be configured as a software algorithm which operates in the host processor or in some other system processor. In this embodiment, the software algorithm selects a Mip-map based upon comparing predefined depth ranges for the Mip-maps with the depth value z for each pixel. In addition, the initial u and v values (and texture width values) are manipulated based upon a calculated shift value to obtain new texture values uxe2x80x2 and vxe2x80x2 (and wxe2x80x2) that then are used to read a texture map.
Further advantages and features of the present invention will become apparent upon reading the detailed description which follows.